package chapter01_stackandqueue;

import java.util.HashMap;
import java.util.Stack;

/**
 * 描述：
 *
 * @author hl
 * @date 2021/1/20 9:53
 */
public class MaxTree {
    /**
     * 单调栈
     *      一个元素左边第一个大于它的结点和
     * @param arr
     * @return
     */
    public static Node maxTree(int[] arr) {
        int length = arr.length;
        Node[] nArr = new Node[length];
        for (int i = 0; i < length; i++) {
            nArr[i] = new Node(arr[i]);
        }
        //左边第一个大于key的结点
        HashMap<Node, Node> lBigMap = new HashMap<>();
        //右边第一个大于key的结点
        HashMap<Node, Node> rBigMap = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            Node curNode = nArr[i];
            while (!stack.isEmpty() && stack.peek().value < curNode.value) {
                Node pop = stack.pop();
                if (!stack.isEmpty()) {
                    lBigMap.put(pop, stack.peek());
                }
                rBigMap.put(pop, curNode);
            }
            stack.push(curNode);
        }
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            if (!stack.isEmpty()) {
                lBigMap.put(pop, stack.peek());
            }
        }
        //开始构建二叉树
        Node head = null;
        for (int i = 0; i < length; i++) {
            Node curNode = nArr[i];
            Node leftNode = lBigMap.get(curNode);
            Node rightNode = rBigMap.get(curNode);
            if (leftNode == null && rightNode == null) {
                head = curNode;
            } else if (leftNode == null) {
                //如果右边第一个大于curNode的结点不为空，必然可以作为左子树挂在rightNode上
                //因为一个结点的任意一边最多只有一个子结点
                rightNode.left = curNode;
            } else if (rightNode == null) {
                leftNode.right = curNode;
            } else {
                if (leftNode.value < rightNode.value) {
                    leftNode.right = curNode;
                } else {
                    rightNode.left = curNode;
                }
            }
        }
        return head;
    }
    public static Node maxTree2(int[] arr) {
        int length = arr.length;
        Node[] nArr = new Node[length];
        for (int i = 0; i < length; i++) {
            nArr[i] = new Node(arr[i]);
        }
        HashMap<Node, Node> lBigMap = new HashMap<>();
        HashMap<Node, Node> rBigMap = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            Node curNode = nArr[i];
            while (!stack.isEmpty() && stack.peek().value < curNode.value) {
                Node pop = stack.pop();
                if (!stack.isEmpty()) {
                    lBigMap.put(pop, stack.peek());
                }
                rBigMap.put(pop, curNode);
            }
            stack.push(curNode);
        }
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            if (!stack.isEmpty()) {
                lBigMap.put(pop, stack.peek());
            }
        }
        //开始构建二叉树
        Node head = null;
        for (int i = 0; i < length; i++) {
            Node curNode = nArr[i];
            Node leftNode = lBigMap.get(curNode);
            Node rightNode = rBigMap.get(curNode);
            if (leftNode == null && rightNode == null) {
                head = curNode;
            } else if (leftNode == null) {
                if(rightNode.left == null){
                    rightNode.left = curNode;
                }else{
                    rightNode.right = curNode;
                }
            } else if (rightNode == null) {
                if (leftNode.right == null) {
                    leftNode.right = curNode;
                }else{
                    leftNode.left = curNode;
                }
            } else {
                Node parent = leftNode.value < rightNode.value ? leftNode : rightNode;
                if(parent.left == null){
                    parent.left = curNode;
                }else{
                    parent.right = curNode;
                }
            }
        }
        return head;
    }

    public static Node popSetMap(Stack<Node> stack, HashMap<Node,Node> map){
        Node curNode = stack.pop();
        if (stack.isEmpty()) {
//            map.put(curNode, null);
        }else{
            map.put(curNode,stack.peek());
        }
        return curNode;
    }
    //二叉树的先序遍历
    public static void printPreOrder(Node head) {
        if (head == null) { return; }
        System.out.print(head.value + " ");
        printPreOrder(head.left);  //递归调用遍历二叉树
        printPreOrder(head.right);
    }

    //二叉树的中序遍历
    public static void printInOrder(Node head) {
        if (head == null) { return; }
        printInOrder(head.left);
        System.out.print(head.value + " ");
        printInOrder(head.right);
    }
    public static void main(String[] args) {
        HashMap<Node, Node> map = new HashMap<>();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        map.put(node1, node2);
        System.out.println(map.get(node1).value);

        int[] arr = {3, 4, 5, 1, 2, 8, 7, 12, 15};
        Node head = maxTree2(arr);
//        printPreOrder(head);
//        System.out.println();
//        printInOrder(head);
        printTree(head);
    }
    public static void printTree(Node head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(Node head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.value + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

}